package algorithm.middle;


/**
 * @author 江岸
 * @version V1.0
 * @ClassName: LengthOfLIS300
 * @description: 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 *
 * 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
 * 输入：nums = [10,9,2,5,3,7,101,18]
 * 输出：4
 * 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/3/49:47
 * @since V1.0
 */
public class LengthOfLIS300 {
    public static void main(String[] args) {
        lengthOfLIS(new int[]{5,7,-24,12,13,2,3,12,5,6,35});
    }

    public static int lengthOfLIS(int[] nums) {
        int res = 0;
        if (nums == null) return res;
        //dp[i]当前下标处的前面的子数组符合条件的元素个数
        int[] dp = new int[nums.length];
        //动态规划，从后往前规划。
        for (int i=nums.length-1;i>-1;i--){
            dp[i] = 1;
            for (int j=i+1;j<nums.length;j++){
                if (nums[j]>nums[i] ){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            res = Math.max(res,dp[i]);
        }
        return res;
    }


    /**
     * 动态规划 二分查找
     */
    public int 官方题解(int[] nums) {
        int len = nums.length;
        if (len <= 1) {
            return len;
        }

        // tail 数组的定义：长度为 i + 1 的上升子序列的末尾最小是几
        int[] tail = new int[len];
        // 遍历第 1 个数，直接放在有序数组 tail 的开头
        tail[0] = nums[0];
        // end 表示有序数组 tail 的最后一个已经赋值元素的索引
        int end = 0;

        for (int i = 1; i < len; i++) {
            // 【逻辑 1】比 tail 数组实际有效的末尾的那个元素还大
            if (nums[i] > tail[end]) {
                // 直接添加在那个元素的后面，所以 end 先加 1
                end++;
                tail[end] = nums[i];
            } else {
                // 使用二分查找法，在有序数组 tail 中
                // 找到第 1 个大于等于 nums[i] 的元素，尝试让那个元素更小
                int left = 0;
                int right = end;
                while (left < right) {
                    // 选左中位数不是偶然，而是有原因的，原因请见 LeetCode 第 35 题题解
                    // int mid = left + (right - left) / 2;
                    int mid = left + ((right - left) >>> 1);
                    if (tail[mid] < nums[i]) {
                        // 中位数肯定不是要找的数，把它写在分支的前面
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                // 走到这里是因为 【逻辑 1】 的反面，因此一定能找到第 1 个大于等于 nums[i] 的元素
                // 因此，无需再单独判断
                tail[left] = nums[i];
            }
            // 调试方法
            // printArray(nums[i], tail);
        }
        // 此时 end 是有序数组 tail 最后一个元素的索引
        // 题目要求返回的是长度，因此 +1 后返回
        end++;
        return end;
    }

    // 调试方法，以观察是否运行正确
    private void printArray(int num, int[] tail) {
        System.out.print("当前数字：" + num);
        System.out.print("\t当前 tail 数组：");
        int len = tail.length;
        for (int i = 0; i < len; i++) {
            if (tail[i] == 0) {
                break;
            }
            System.out.print(tail[i] + ", ");
        }
        System.out.println();
    }

    public int fun(int[] nums) {
        int len = nums.length;
        if (nums.length<=1){
            return len;
        }
        int[] tail = new int[len];
        int end = 0;
        tail[0] = nums[0];
        end++;
        for (int i=1;i<len;i++){
            if (nums[i]>tail[end-1]){
                //当前数大于tail末尾数，直接往后添加
                tail[end] = nums[i];
                end++;
            }else {
                //二分查找 找到一个刚好大于nums[i]的数
                int left = 0;
                int right = end;
                int mid;
                while (left<right){
                    mid = left + ((right-left)>>>1);
                    if (tail[mid]<nums[i]){
                        left = mid+1;
                    }else {
                        right = mid;
                    }
                }
                tail[left] = nums[i];
            }
        }
        return end;
    }

}
